#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <windows.h>
 
void PrintArr( int arr[], int iSize )
{
	if( iSize < 0 )
		return;
	
	int i = 0;
	for( ; i < iSize; i++ )
	{
		if( !arr[i] )
			printf( "%d ", arr[i] );
	}
 
	puts( "" );
}
 
void LocalMove( int arr[], int iSize )
{//本地移动 速度极慢 优点是消耗内存空间少
	if( iSize <= 1 )
		return;
 
	int i,j;
 
	int iZeroCount = 0;//零元总数
 
	for( i = 0; i < iSize; i++ )
	{
		if( !arr[i] )
			iZeroCount++;
	}
 
	int iZeroCur = iZeroCount;
	
	for( i  = 0; i < iSize && iZeroCur > 0; i++ )
	{
		if( !arr[i] )
		{
			for( j = i; j < iSize - ( iZeroCount - iZeroCur ); j++ )
			{
				arr[j] = arr[j+1];
			}
 
			arr[j-1] = 0;
			iZeroCur--;
			i--;
		}
	}
 
	//PrintArr( arr, iSize );
}
 
int* CreateIntArr( int iSize )
{//创建整形数组
	puts( "CreateArr" );
 
	int* pIntArr = (int*)malloc( sizeof( int ) * iSize );
 
	if( !pIntArr )
		return NULL;
 
	srand( iSize );
 
	int i = 0;
	for( ; i < iSize; i++ )
	{
		if( 0 == i % 2 )
			*( pIntArr + i ) = rand();
		else
			*( pIntArr + i ) = 0;
	}
 
	puts( "Finish create array!" );
 
	return pIntArr;	
}
 
int* CopyArr( int* pArrInt, int iSize )
{//复制整形数组
	if( !pArrInt || iSize <= 0 )
		return  NULL;
 
	int* pNewArr = (int*)malloc( sizeof( int ) * iSize );
 
	if( !pNewArr )
		return NULL;
 
	puts( "Starting copy array ..." );
	int i = 0;
	for( ; i < iSize; i++ )
	{
		*( pNewArr + i ) = *( pArrInt + i );
	}
 
	puts( "Finish copy array..." );
 
	return pNewArr;
}
void SaveMove( int arr[], int iSize )
{//空间换时间 这个算法的速度是上个算法速度的8万倍以上 这个专卖值得做
	if( iSize <= 1 )
		return;
 
	int i  = 0;
	int iNoneZero = 0;
 
	for( ; i < iSize; i++ )
	{
		if( arr[i] )
			iNoneZero++;
	}
 
	int* pIntArr = (int*)malloc( sizeof( int ) * iNoneZero );
	int iCur = 0;
	for( i = 0; i < iSize && iNoneZero > 0; i++ )
	{
		if( arr[i] )
		{
			*(pIntArr + iCur++) = arr[i];
			iNoneZero--;
		}
	}
	
	memset( arr, 0, iSize );
	for( i = 0; i < iCur; i++ )
	{
		arr[i] = *( pIntArr + i );
	}
 
	//PrintArr( arr, iSize );
}
 
 
 
int main( int argc, char* argv[] )
{
	if( argc < 2 )
	{
		puts( "Usage: MoveZero.exe number" );
		return -1;
	}
 
	int iNum = atoi( argv[1] );
 
	if( iNum <= 0 )
	{
		puts( "Error argument!" );
	}
 
	int* pIntArrOne = CreateIntArr( iNum );
	int* pIntArrTwo = CopyArr( pIntArrOne, iNum );
 
	long lStart;
	
	lStart = GetTickCount();
	puts( "LocalMove" );
	LocalMove( pIntArrOne, iNum );
	printf( "LocalMove Cost Time: %ld\n", GetTickCount() - lStart );
 
	lStart = GetTickCount();
	puts( "SaveMove" );
	SaveMove( pIntArrTwo, iNum );
	printf( "SaveMove Cost Time: %ld\n", GetTickCount() - lStart );
 
	return 0;
}